Chuyển đổi từ Dạng Hậu tố sang Dạng Tiền tố

Mục tiêu

Mục tiêu của bạn là chuyển đổi một biểu thức hậu tố (Dạng đảo ngược của Notation Ba Lan) thành dạng tương đương biểu thức tiền tố (Dạng Ba Lan) bằng cách xây dựng và duyệt cây biểu thức.

Thuật toán

1. Xây dựng cây biểu thức: Xử lý biểu thức hậu tố từ trái sang phải bằng cách sử dụng ngăn xếp.
   • Khi gặp một toán hạng (ví dụ: A, B) được tìm thấy, hãy tạo một cây đơn nút cho nó và đẩy vào ngăn xếp.
   • Khi gặp một toán tử (ví dụ: +, *) được tìm thấy, lấy hai cây từ ngăn xếp. Cây lấy ra đầu tiên là con phải (T₂) và cây thứ hai là con trái (T₁). Tạo một cây mới với toán tử làm gốc và đẩy lại vào ngăn xếp.
2. Tạo chuỗi biểu thức tiền tố: Sau khi xử lý tất cả các token, ngăn xếp sẽ chứa cây biểu thức hoàn chỉnh. Thực hiện phép duyệt tiền thứ tự (Gốc → Trái → Phải) trên cây này để tạo ra biểu thức tiền tố cuối cùng.

Ví dụ

Với biểu thức hậu tố A B + C *, thuật toán sẽ xây dựng cây sau:

  *
   / \
  +   C
 / \
A   B

Phép duyệt tiền thứ tự cho ra biểu thức tiền tố: * + A B C.

Định dạng đầu vào/đầu ra

Đầu vào

• Dòng 1: Một số nguyên N (1 ≤ N ≤ 1000), số lượng token.
• Dòng 2: Biểu thức hậu tố, gồm N token được phân cách bởi dấu cách.

Quy tắc token

• Toán hạng: Các chữ cái in hoa duy nhất (A-Z).
• Toán tử: Bốn toán tử nhị phân: +, -, *, /.

Đầu ra

• Một dòng duy nhất chứa biểu thức tiền tố tương ứng, các token được phân cách bởi dấu cách.

Các ví dụ

Ví dụ 1:

5

A B + C *

* + A B C

Ví dụ 2:

7

A B C * + D /

/ + A * B C D

Ví dụ 3:

7

A B + C D - *

* + A B - C D

Giới hạn